Lecture: TuTh 3:30 PM - 4:59 PM in Li Ka Shing 245
Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani (DPV)
For this semester, we unfortunately currently no longer plan to publish lectures to YouTube. The lectures playlist can still be found on bCourses in the Media Gallery tab (CalNet CAS required). Please refer to the playlist for the most up-to-date lectures available.
Please be informed that access to the majority of solutions on this website necessitates authentication through CalNet CAS. Should you require access to these restricted materials but do not possess a CalNet ID, kindly contact us for further assistance.
Week | Date | Lecture | Reading | Section | Assignments |
---|---|---|---|---|---|
1 |
Tu 1/16 |
1: Introduction, Big-O Notation, Arithmetic slidesslides (6up) recording posted! |
DPV
§0
,
§1.1
|
||
Th 1/18 |
2: Integer Multiplication, Recurrence Relations, Master Theorem slidesslides (6up) recording posted! |
DPV
§2.1
,
§2.2
|
|||
2 |
Tu 1/23 |
3: Matrix Muliplication, Median-Finding slidesslides (6up) recording posted! |
DPV
§2.3
,
§2.4
,
§2.5
|
HW 1
due 1/29 |
|
Th 1/25 |
4: Fast Fourier Transform (Part I) slidesslides (6up) recording posted! |
DPV
§2.6
|
|||
3 |
Tu 1/30 |
5: Fast Fourier Transform (Part II) slidesslides (handout) recording posted! |
DPV
§2.6
|
||
Th 2/1 |
6: Depth First Search, Topological Sort slidesslides (handout) recording posted! |
DPV
§3
|
|||
4 |
Tu 2/6 |
7: Strongly Connected Components slidesrecording posted! |
DPV
§3
|
||
Th 2/8 |
8: Paths in Graphs slidesrecording posted! |
DPV
§4
FFT Applications |
|||
5 |
Tu 2/13 |
9: Greedy Algorithms, Huffman encoding slidesrecording posted! |
DPV
§5
,
§5.2
|
||
Th 2/15 |
10: Minimum Spanning Trees slidesprim's proof recording posted! |
DPV
§5.1
|
|||
6 |
Tu 2/20 |
11: Union Find, Horn Formulas slidesrecording posted! |
DPV
§5.1.4
,
§5.3
|
||
Th 2/22 |
12: Dynamic Programming (Part I) slidesrecording posted! |
DPV
§6.1
,
§6.2
,
§6.3
|
|||
7 |
Tu 2/27 |
Midterm 1 on 2/26 |
|||
Th 2/29 |
13: Dynamic Programming (Part II) slidesrecording posted! |
DPV
§6.3
,
§6.4
|
|||
8 |
Tu 3/5 |
14: Dynamic Programming (Part III) slidesrecording posted! |
DPV
§6.6
|
||
Th 3/7 |
15: Dynamic Programming (Part IV) slidesrecording posted! |
DPV
§6.5
,
§6.6
,
§6.7
|
|||
9 |
Tu 3/12 |
16: Linear Programs, Simplex Algorithm slidesrecording posted! |
DPV
§7.1
|
||
Th 3/14 |
17: Network Flow, Bipartite Matching slidesrecording posted! |
DPV
§7.2
,
§7.3
|
|||
10 |
Tu 3/19 |
18: Duality, Zero-Sum Games slidesrecording posted! |
DPV
§7.4
,
§7.5
|
||
Th 3/21 |
19: Review slidesrecording posted! |
||||
11 |
Tu 3/26 |
Spring Recess |
|||
Th 3/28 |
Spring Recess |
||||
12 |
Tu 4/2 |
Midterm 2 |
|||
Th 4/4 |
20: Reductions, NP-Completeness slidesrecording posted! |
DPV
§7.3
,
§8.1
|
|||
13 |
Tu 4/9 |
21: Reductions slidesrecording posted! |
DPV
§8.2, 8.3
|
||
Th 4/11 |
22: Coping with NP-completeness slidesrecording posted! |
DPV
§9
|
|||
14 |
Tu 4/16 |
23: Coping with NP-completeness slidesrecording posted! |
DPV
§9
|
||
Th 4/18 |
24: Gradient Descent (Part I) slidesrecording posted! |
GD Notes (sections 1-3) -- updated 4/29
|
|||
15 |
Tu 4/23 |
25: Gradient Descent (Part II) slidesrecording posted! |
GD Notes -- updated 4/29
|
||
Th 4/25 |
26: Gradient Descent (Part III), Multiplicative Weights |
GD Notes -- updated 4/29
|